The global positioning system (GPS) is a satellite-based radio-navigation system built and operated by the United States Department of Defense. The system uses twenty-four satellites orbiting the earth at an altitude of about 11,000 miles with a period of about twelve hours. Some additional satellites may be present as spares. These satellites are placed in six different orbits such that at any time a minimum of six satellites are visible at any location on the surface of the earth except in the polar region. Each satellite transmits a time and position signal referenced to an atomic clock. A typical GPS receiver locks onto this signal and extracts the data contained in it. Using signals from a sufficient number of satellites, a GPS receiver can calculate its position, velocity, altitude, and time.
Data is modulated to the GPS signal, in which each data bit spans 20 milliseconds. This data contains ephemeris that provides satellite orbit information and time information to help the receiver determine the system time. Under weak signal conditions, it is still possible for the receiver to acquire and track the GPS signal with a longer non-coherent integration time or other method. However, due to the low signal to noise ratio, the error rate of the decoded GPS broadcast data will be too high making it impossible to determine the signal transmit time. Under this condition, the traditional position calculation method can not be applied.
Some prior art references have been published that deal with the above conditions. The central concept of these methods is adding another variable as system time to compensate for the uncertainty of the signal transmit time. An additional observation measurement is required to help to solve the additional variable. As a result measurements of at least five satellites are needed to calculate the final position.
When the signal transmit time can not be determined, it is impossible to calculate the pseudo-range with the traditional method of multiplying the speed of light with the difference between the signal transmit time and receive time. Because only the C/A code is tracked, only a sub-millisecond fraction of the transmit time can be determined. As a result, the calculated pseudo-range will have 300 km ambiguity, which is the distance the signal travels in one millisecond.
Given an estimated pseudo-range of one satellite ρi, the pseudo-range can be divided into a millisecond part and a sub-millisecond part, ρi=ρi(1)+ρi(2), where
            ρ      i              (        1        )              =          Λ      ×              ⌊                              ρ            i                    Λ                ⌋              ,            ρ      i              (        2        )              =                  ρ        i            -                        ρ          i                      (            1            )                          .            The symbol └ ┘ indicates to take the integer value of the division. The symbol Λ is the distance light travels in 1 ms and is about 300 km. Under weak signal conditions, only the sub-millisecond part ρi(2) can be obtained. The millisecond part ρi(1) can be estimated and used to calculate the pseudo-range ρi by carrying out the following steps:
Make an estimation of the GPS time of signal arrival Tu.
Estimate the travel time of the signal tf. If the travel time can not be estimated, use 70 ms as an approximation for tf.
Calculate the satellite position at time Tu−tf as (Tu-tf), where ( ) is the satellite position as a function of time, which may be derived from ephemeris downloaded onto the receiver.
Use the estimated user position  to calculate the millisecond part of the pseudorange as:
            ρ      i              (        1        )              =          Λ      ×              ⌊                                                                                                                                      s                      ⇀                                        i                                    ⁡                                      (                                                                  T                        u                                            -                                              t                        f                                                              )                                                  -                                  u                  ⇀                                                                    +                          ct              u                                Λ                ⌋              ,where tu is the receiver clock offset.
Sum the parts ρi(1) and ρi(2) together to get ρi=ρi(1)+ρi(2).
Although a precise determination of the receiver clock offset tu should include the same information as a precise determination of what is here called the GPS time at arrival Tu (in the sense that if you know tu precisely, you should know Tu), the GPS time at arrival as used here likely does not convey the same information as the receiver clock offset. Thus, the GPS time at arrival is treated as independent of the receiver clock offset. By introducing the GPS time at arrival Tu as one additional degree of freedom for the solution of the PVT equation, at least five satellites need to be tracked to solve the PVT. The equations are shown by the following:
At time Tu-tf the position of the ith satellite is , and the speed of the ith satellite is , where i is used for a satellite index.
The initial receiver position is  and initial clock offset is {circumflex over (t)}u.
An initial range {circumflex over (ρ)}i can be written as {circumflex over (ρ)}i={circumflex over (r)}i+c{circumflex over (t)}u, where {circumflex over (r)}i=∥−∥. The unit vector of {circumflex over (r)}i is
                    a        ⇀            i        =                                                      s              ⇀                        i                    -                      u                          ⇀              ^                                                            r            ^                    i                    =                                    a            xi                    ·                      x            ⇀                          +                              a            yi                    ·                      y            ⇀                          +                              a            zi                    ·                      z            ⇀                                ,in which ,  and  correspond to the x, y and z axis. The difference between the initial range {circumflex over (ρ)}i and the range ρi to be solved is Δρi={circumflex over (ρ)}i−ρi={circumflex over (r)}i+c{circumflex over (t)}u−ρi. The solution using five satellites can be given by:
            Δ      ⁢                          ⁢              ρ        ⇀              =          [                                                  Δρ              1                                                                          Δρ              2                                                                          Δρ              3                                                                          Δρ              4                                                                          Δρ              5                                          ]            H    =                            [                                                                      a                                      x                    ⁢                                                                                  ⁢                    1                                                                                                a                                      y                    ⁢                                                                                  ⁢                    1                                                                                                a                                      z                    ⁢                                                                                  ⁢                    1                                                                                                                                          a                      ⇀                                        1                                    ·                                                            v                      ⇀                                        1                                                                              1                                                                                      a                                      x                    ⁢                                                                                  ⁢                    2                                                                                                a                                      y                    ⁢                                                                                  ⁢                    2                                                                                                a                                      z                    ⁢                                                                                  ⁢                    2                                                                                                                                          a                      ⇀                                        2                                    ·                                                            v                      ⇀                                        2                                                                              1                                                                                      a                                      x                    ⁢                                                                                  ⁢                    3                                                                                                a                                      y                    ⁢                                                                                  ⁢                    3                                                                                                a                                      z                    ⁢                                                                                  ⁢                    3                                                                                                                                          a                      ⇀                                        3                                    ·                                                            v                      ⇀                                        3                                                                              1                                                                                      a                                      x                    ⁢                                                                                  ⁢                    4                                                                                                a                                      y                    ⁢                                                                                  ⁢                    4                                                                                                a                                      z                    ⁢                                                                                  ⁢                    4                                                                                                                                          a                      ⇀                                        4                                    ·                                                            v                      ⇀                                        4                                                                              1                                                                                      a                                      x                    ⁢                                                                                  ⁢                    5                                                                                                a                                      y                    ⁢                                                                                  ⁢                    5                                                                                                a                                      z                    ⁢                                                                                  ⁢                    5                                                                                                                                          a                      ⇀                                        5                                    ·                                                            v                      ⇀                                        5                                                                              1                                              ]                ⁢                                  ⁢        and        ⁢                                  ⁢        Δ        ⁢                                  ⁢                  x          ⇀                    =              [                                                            Δ                ⁢                                                                  ⁢                                  x                  u                                                                                                        Δ                ⁢                                                                  ⁢                                  y                  u                                                                                                        Δ                ⁢                                                                  ⁢                                  z                  u                                                                                                        Δ                ⁢                                                                  ⁢                                  T                  u                                                                                                        -                                  ct                  u                                                                    ]            
which gives Δ=HΔ.
With more than five satellites, we can use least square method to get the solution.
Because of the ambiguity of Λ in the pseudo-range calculation, the estimated user position and time should not be too far away from the true value, otherwise, the millisecond part of ρi(1) will have and incorrect value and result in an incorrect receiver position calculation. This limitation gives a restriction on the initial position and initial time of
            κ      ·              (                              T            u                    -                                    T              ^                        u                          )              +                                  u          ⇀                -                  u                      ⇀            ^                                      <            Λ      2        .  Here Tu and  are the true signal arrive time and receiver position respectively, {circumflex over (T)}u and  are estimated initial signal arrive time and receiver position respectively, and κ is the maximum possible pseudo-range change rate (about 710 m/s).
If the above condition can not be met, several methods can be applied to help remove the ambiguity of the pseudo-range. One of these methods is to introduce one or more additional observation measurements so the number of equations in Δ=HΔ is more than the number of variables. When using the least square method to solve the equations, we can get a residual of the solution. A grid is applied to the possible area covering the possible initial position. With all the possible initial positions and signal arrival times, the residual will reach the global minimum with the correct combination. These combinations should cover the span of all possible estimated signal arrival times and the area around the surface of the earth that can see all the satellites. Because this algorithm searches all the possible solutions and finds the minimum one, the computation time is significant and performing a position fix on an embedded computing system in a limited time is not practical.
Several publications discuss the above methods. A method using five satellites to perform the position fix is disclosed in U.S. Pat. Nos. 6,215,442 B1, and 6,437,694 B1 discloses a method using Kalman filter. Methods using six or more satellites that find the minimum residual result as the final solution are described in U.S. Pat. Nos. 6,417,801 B1 and 6,734,821 B2. In U.S. Pat. No. 6,865,478 B2, a method is given to reduce the possible initial positions to reduce the computation time. U.S. Pat. No. 6,670,916 gives a height constraint condition so that four satellites can be used to compute the position.
When the initial position and time is unknown or is less accurate such that the condition of
            κ      ·              (                              T            u                    -                                    T              ^                        u                          )              +                                  u          ⇀                -                  u                      ⇀            ^                                      <      Λ    2  can not be met, none of above methods can be applied to calculate receiver position within a reasonable computation time especially for embedded electrical devices.
Accordingly, there is a need for determining an initial position and time that is accurate enough to be used as a starting point to calculate the receiver position, and that can be performed within a reasonable computation time. This would provide relatively accurate initial position and time to meet the requirement of
            κ      ·              (                              T            u                    -                                    T              ^                        u                          )              +                                  u          ⇀                -                  u                      ⇀            ^                                      <      Λ    2  to perform further position calculations.